package leecode.二叉树;

import util.ListNode;

/**
 * @author wangxi created on 2021/6/8 00:06
 * @version v1.0
 *
 * https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
 *
 * 参照官方题解
 *
 * 为什么要设定「左闭右开」的关系？由于题目中给定的链表为单向链表，访问后继元素十分容易，但无法直接访问前驱元素。
 * 因此在找出链表的中位数节点mid 之后，如果设定「左闭右开」的关系，
 * 我们就可以直接用 (left,mid) 以及 (mid.next,right) 来表示左右子树对应的列表了。
 * 并且，初始的列表也可以用(head,null) 方便地进行表示，其中 null 表示空节点。
 *
 */
public class SortedListToBST {

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        return help(head, null);
    }

    private TreeNode help(ListNode left, ListNode right) {
        if (left == right) {
            // 在左闭右开的区间，走到这里说明链表已经没有节点了
            return null;
        }
        ListNode mid = findMid(left, right);
        TreeNode root = new TreeNode(mid.val);
        root.left = help(left, mid);
        root.right = help(mid.next, right);
        return root;
    }

    // 需要限制 头尾边界，因为mid节点被当做root节点后，这个节点就需要再充当找中间节点的链表丢弃掉，否则递归就无法退出了
    private ListNode findMid(ListNode left, ListNode right) {
        ListNode slow = left;
        ListNode fast = left;
        while (slow != right && fast != right && fast.next != right && fast.next.next != right) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
